package com.lw.leetcode.arr.b;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * 743. 网络延迟时间
 *
 * @author liw
 * @version 1.0
 * @date 2021/8/2 11:09
 */
public class NetworkDelayTime {

    public static void main(String[] args) {
        NetworkDelayTime test = new NetworkDelayTime();

        // 输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2  2
        int[][] arr = {{2,1,1}, {2,3,1}, {3,4,1}};
        int n = 4;
        int k = 2;


        // [[1,2,1],[2,1,3]] 2 2     3
//        int[][] arr = {{1,2,1}, {2,1,3}};
//        int n = 2;
//        int k = 2;

        // [[1,2,1],[2,3,2],[1,3,2]] 3 1   2
//        int[][] arr = {{1,2,1}, {2,3,2}, {1,3,2}};
//        int n = 3;
//        int k = 1;

        // [[1,2,1],[2,3,7],[1,3,4],[2,1,2]] 3 1   4
//        int[][] arr = {{1, 2, 1}, {2, 3, 7}, {1, 3, 4}, {2, 1, 2}};
//        int n = 3;
//        int k = 1;


        // [[1,2,1],[2,3,7],[1,3,4],[2,1,2]] 3 2   6
//        int[][] arr = {{1, 2, 1}, {2, 3, 7}, {1, 3, 4}, {2, 1, 2}};
//        int n = 3;
//        int k = 2;

        int i = test.networkDelayTime(arr, n, k);
        System.out.println(i);

        System.out.println(Arrays.toString(test.arr));

    }

    private Map<Integer, List<int[]>> map;
    private int[] arr;

    public int networkDelayTime(int[][] times, int n, int k) {
        arr = new int[n + 1];
        Arrays.fill(arr, -1);
        Map<Integer, List<int[]>> m = new HashMap<>();
        for (int[] time : times) {
            m.computeIfAbsent(time[0], v -> new ArrayList<>()).add(time);
        }
        this.map = m;
        arr[k] = 0;
        arr[0] = 0;
        find(k, 0);
        int max = 0;
        for (int i : arr) {
            if (i == -1) {
                return -1;
            }
            max = Math.max(max, i);
        }
        return max;
    }

    private void find(int k, int item) {
        List<int[]> list = map.get(k);
        if (list == null) {
            return;
        }
        for (int[] ints : list) {
            int value = item + ints[2];
            int next = ints[1];
            if (arr[next] != -1 && arr[next] <= value) {
                continue;
            }
            arr[next] = value;
            find(next, value);
        }
    }
}
